#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100
#define INF 999999

// 图的结构定义
typedef struct
{
    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
    int vexnum;                                // 顶点数
} Graph;

// 队列结构定义
typedef struct
{
    int data[MAX_VERTICES];
    int front, rear;
} Queue;

// 全局变量
int d[MAX_VERTICES];        // 距离数组
int path[MAX_VERTICES];     // 路径数组
bool visited[MAX_VERTICES]; // 访问标记数组

// 队列操作函数
void InitQueue(Queue *Q)
{
    Q->front = Q->rear = 0;
}

bool isEmpty(Queue *Q)
{
    return Q->front == Q->rear;
}

void EnQueue(Queue *Q, int x)
{
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAX_VERTICES;
}

int DeQueue(Queue *Q)
{
    int x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_VERTICES;
    return x;
}

// 获取第一个邻接顶点
int FirstNeighbor(Graph G, int u)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (G.adjMatrix[u][i] != 0)
        {
            return i;
        }
    }
    return -1;
}

// 获取下一个邻接顶点
int NextNeighbor(Graph G, int u, int w)
{
    for (int i = w + 1; i < G.vexnum; i++)
    {
        if (G.adjMatrix[u][i] != 0)
        {
            return i;
        }
    }
    return -1;
}

// 求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u)
{
    Queue Q;
    InitQueue(&Q);

    // d[i]表示从u到i顶点的最短路径
    for (int i = 0; i < G.vexnum; ++i)
    {
        d[i] = INF;         // 初始化路径长度
        path[i] = -1;       // 最短路径从哪个顶点过来
        visited[i] = false; // 初始化访问标记
    }

    d[u] = 0;
    visited[u] = true;
    EnQueue(&Q, u);

    while (!isEmpty(&Q))
    {                              // BFS算法主过程
        int current = DeQueue(&Q); // 队头元素u出队

        for (int w = FirstNeighbor(G, current); w >= 0; w = NextNeighbor(G, current, w))
        {
            if (!visited[w])
            {                          // w为u的尚未访问的邻接顶点
                d[w] = d[current] + 1; // 路径长度加1
                path[w] = current;     // 最短路径应从current到w
                visited[w] = true;     // 设已访问标记
                EnQueue(&Q, w);        // 顶点w入队
            }
        }
    }
}

// 初始化图
void InitGraph(Graph *G)
{
    printf("请输入顶点数: ");
    scanf("%d", &G->vexnum);

    // 初始化邻接矩阵
    for (int i = 0; i < G->vexnum; i++)
    {
        for (int j = 0; j < G->vexnum; j++)
        {
            G->adjMatrix[i][j] = 0;
        }
    }

    printf("请输入边数: ");
    int edgeNum;
    scanf("%d", &edgeNum);

    printf("请输入边的信息 (格式: 起点 终点):\n");
    for (int i = 0; i < edgeNum; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        G->adjMatrix[u][v] = 1; // 有向图
        G->adjMatrix[v][u] = 1; // 如果是无向图，添加这行
    }
}

// 打印最短路径
void PrintPath(int start, int end)
{
    if (d[end] == INF)
    {
        printf("从顶点%d到顶点%d没有路径\n", start, end);
        return;
    }

    printf("从顶点%d到顶点%d的最短距离: %d\n", start, end, d[end]);
    printf("路径: ");

    // 递归打印路径
    int pathArray[MAX_VERTICES];
    int pathLength = 0;
    int current = end;

    while (current != -1)
    {
        pathArray[pathLength++] = current;
        current = path[current];
    }

    // 逆序打印路径
    for (int i = pathLength - 1; i >= 0; i--)
    {
        printf("%d", pathArray[i]);
        if (i > 0)
            printf(" -> ");
    }
    printf("\n");
}

// 打印所有最短距离
void PrintAllDistances(int start, Graph G)
{
    printf("\n从顶点%d到各顶点的最短距离:\n", start);
    for (int i = 0; i < G.vexnum; i++)
    {
        if (i != start)
        {
            if (d[i] == INF)
            {
                printf("到顶点%d: 无路径\n", i);
            }
            else
            {
                printf("到顶点%d: %d\n", i, d[i]);
            }
        }
    }
}

int main()
{
    Graph G;

    printf("=== BFS最短路径算法 ===\n");
    InitGraph(&G);

    int startVertex;
    printf("请输入起始顶点: ");
    scanf("%d", &startVertex);

    if (startVertex < 0 || startVertex >= G.vexnum)
    {
        printf("起始顶点输入错误!\n");
        return -1;
    }

    // 执行BFS求最短路径
    BFS_MIN_Distance(G, startVertex);

    // 打印所有距离
    PrintAllDistances(startVertex, G);

    // 查询特定路径
    char choice;
    printf("\n是否要查询特定路径? (y/n): ");
    scanf(" %c", &choice);

    while (choice == 'y' || choice == 'Y')
    {
        int endVertex;
        printf("请输入目标顶点: ");
        scanf("%d", &endVertex);

        if (endVertex >= 0 && endVertex < G.vexnum)
        {
            PrintPath(startVertex, endVertex);
        }
        else
        {
            printf("目标顶点输入错误!\n");
        }

        printf("继续查询其他路径? (y/n): ");
        scanf(" %c", &choice);
    }

    return 0;
}

/*
示例输入:
顶点数: 6
边数: 7
边的信息:
0 1
0 2
1 3
2 3
2 4
3 5
4 5
起始顶点: 0

这将创建一个图:
    0
   / \
  1   2
   \ /|\
    3  4
     \/
      5
*/